#include <stdio.h>
#include <stdlib.h>

// step 1# 定义哈希节点类型 和 哈希函数
typedef struct {
    int key;
    int value;
} HashNode;

int hashFunction(int key, int hashSize) {
    long long tmp = (long long)key;
    if (tmp < 0) tmp = -tmp;
    return tmp % hashSize;
};

int *twoSum(int *nums, int numsSize, int target, int *returnSize) {
    // step 2# 初始化哈希表
    int hashSize = numsSize * 2;
    HashNode *hashTable = (HashNode *)malloc(sizeof(HashNode) * hashSize);
    for(int i = 0; i < hashSize; i++) {
        hashTable[i].key = 0;
        hashTable[i].value = -1;
    }
    // step 3# 遍历数组：对数组每个元素求补数，然后在哈希表中查补数
    for(int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        int comIndex = hashFunction(complement, hashSize);
        // step 3.1# 哈希表查补数时，用线性探测解决哈希冲突
        while(hashTable[comIndex].value != -1) {
            if (hashTable[comIndex].key == complement) {
                int *res = (int *)malloc(sizeof(int) * 2);
                res[0] = i;
                res[1] = hashTable[comIndex].value;
                *returnSize = 2;
                return res;
            }
            comIndex = (comIndex + 1) % hashSize;
        }
        // step 4# 如果补数在哈希表中没找到，就把当前数组元素加入哈希表
        int numsIndex = hashFunction(nums[i], hashSize);
        // step 4.1# 用线性探测解决哈希冲突
        while(hashTable[numsIndex].value != -1) {
            numsIndex = (numsIndex + 1) % hashSize;
        }
        hashTable[numsIndex].key = nums[i];
        hashTable[numsIndex].value = i;
    }
    
    // step 5# 如果数组遍历完还没有在哈希表找到补数，则返回 NULL
    *returnSize = 0;
    return NULL;
}